package main
func inorderSuccessor(root, p *TreeNode) (parent *TreeNode) {
	//只用在遍历过程中维护此节点，和此节点前一个节点就行
	//st :=[]*TreeNode{}
	//var pre,cur *TreeNode = nil,root
	//for len(st) >0 ||cur !=nil{
	//	for cur !=nil{
	//		st =append(st,cur)
	//		cur =cur.Left
	//	}
	//	cur =st[len(st)-1]
	//	st =st[:len(st)-1]
	//	if pre ==p{
	//		return cur
	//	}
	//	pre =cur
	//	cur =cur.Right
	//}
	//return nil

	//左子树不空，则左子树上所有节点的值均小于它的根节点的值，
	//右子树不空，则右子树上所有节点的值大于它的根节点的值
	//1.当要查的p节点的值大于当前遍历的节点的值，说明后续节点一定在右子树，对右子树进行遍历
	//2.反之可得，否则对左子树进行遍历，如果最终查到的值不存在，返回当前节点，否则返回查找到的节点
	node :=root
	for node != nil {
		if node.Val <=p.Val{
			node =node.Right
		}else{
			parent,node =node,node.Left
		}
	}
	if node == nil{
		return parent
	}
	return nil
}

